The present invention relates to trellis coded quadrature amplitude modulation (QAM) and more particularly to a practical method for coding 16 and 64 QAM transmission to enable a low-cost implementation of a digital cable television system or the like.
Digital data, for example digitized video for use in broadcasting digitized conventional or high definition television (HDTV) signals, can be transmitted over satellite, terrestrial or cable VHF or UHF analog channels for communication to end users. Analog channels deliver corrupted and transformed versions of their input waveforms. Corruption of the waveform, usually statistical, may be additive and/or multiplicative, because of possible background thermal noise, impulse noise, and fades. Transformations performed by the channel are frequency translation, nonlinear or harmonic distortion and time dispersion.
In order to communicate digital data via an analog channel, the data is modulated using, for example, a form of pulse amplitude modulation (PAM). Typically, quadrature amplitude modulation (QAM) is used to increase the amount of data that can be transmitted within an available channel bandwidth. QAM is a form of PAM in which a plurality of bits of information are transmitted together in a pattern referred to as a "constellation" that can contain, for example, sixteen, thirty-two or sixty-four points. An example of a system for communicating digital data using QAM, and specifically trellis coded QAM, is provided in U.S. Pat. No. 5,233,629 to Paik, et al., incorporated herein by reference.
In pulse amplitude modulation, each signal is a pulse whose amplitude level is determined by a transmitted symbol. In 16-bit QAM, symbol amplitudes of -3, -1, 1 and 3 in each quadrature channel (I and Q) are typically used. Bandwidth efficiency in digital communication systems is defined as the number of transmitted bits per second per unit of bandwidth, i.e., the ratio of the data rate to the bandwidth. Modulation systems with high bandwidth efficiency are employed in applications that have high data rates and small bandwidth occupancy requirements. One such application is the transmission of television signals in a standard 6 MHz or so bandwidth. QAM provides bandwidth efficient modulation that is useful for such applications.
Trellis coded modulation (TCM) has evolved as a combined coding and modulation technique for digital transmission over band limited channels. It allows the achievement of significant coding gains over conventional uncoded multilevel modulation, such as QAM, without compromising bandwidth efficiency. TCM schemes utilize redundant nonbinary modulation in combination with a finite-state encoder which governs the selection of modulation signals to generate coded signal sequences. In the receiver, the noisy signals are decoded by a soft-decision maximum likelihood sequence decoder. Such schemes can improve the robustness of digital transmission against additive noise by 3-6 dB or more, compared to conventional uncoded modulation. These gains are obtained without significant bandwidth expansion or reduction of the effective information rate as required by other known error correction schemes. The term "trellis" is used because these schemes can be described by a state-transition (trellis) diagram similar to the trellis diagrams of binary convolutional codes. The difference is that TCM extends the principles of convolutional coding to nonbinary modulation with signal sets of arbitrary size.
For applications that are band limited, and require low cost components (particularly low cost data decoders), conventional QAM systems have not been feasible due to the complexity and relatively high cost of the required encoder and decoder circuits. In fact, it is typical to implement QAM trellis encoders and decoders in expensive custom integrated circuit chips.
One band limited application in which a low cost solution is necessary for communicating digital data is the digital communication of cable television signals, which may include compressed conventional or high definition television signals. Systems for transmitting such signals have data rate requirements on the order of 15-30 megabits per second (Mbps), bandwidth occupancy requirements on the order of 6 MHz (the bandwidth of a conventional National Television System Committee (NTSC) television channel), and very high data reliability requirements (i.e., a very small bit error rate). The data rate requirement arises from the need to provide a high quality compressed television picture. The bandwidth constraint is a consequence of the U.S. Federal Communications Commission requirement that such signals occupy existing 6 MHz television channels, and must coexist with the current broadcast NTSC signals. Similar constraints are mandated by the PAL (Phase Alternating Line) and SECAM (Sequential Color and Memory) television systems used outside the U.S.
The combination of data rate and bandwidth occupancy requirements mandated by the standard television transmission systems dictates a modulation system that has high bandwidth efficiency. Indeed, the ratio of data rate to bandwidth must be on the order of 3 to 6. This means that a bandwidth efficient modulation such as QAM is required. However, as noted above, QAM systems have been too expensive to implement for high volume consumer applications.
The requirement for a very high data reliability in digitized video applications results from the fact that highly compressed source material (i.e., the compressed video) is intolerant of channel errors. The natural redundancy of the signal has been removed in order to obtain a concise description of the intrinsic value of the data. For example, for a system to transmit at 15 Mbps for a twenty-four hour period, with less than one bit error, requires the bit error rate (BER) of the system to be less than one error in 10.sup.12 transmitted bits.
Data reliability requirements are often met in practice via the use of concatenated coding techniques, which is a divide and concur approach to problem solving. In such a coding framework, two codes are employed. An "inner" modulation code cleans up the channel and delivers a modest symbol error rate to an "outer" decoder. The inner code is usually a coded modulation that can be effectively decoded using "soft decisions" (i.e., finely quantized channel data). A known approach is to use a convolutional or trellis code as the inner code with some form of the "Viterbi algorithm" as a trellis decoder. The outer code is most often a t-error-correcting, "Reed-Solomon" code. Such Reed-Solomon coding systems, that operate in the data rate range required for communicating digital television data, are widely available and have been implemented in the integrated circuits of several vendors. The outer decoder removes the vast majority of symbol errors that have eluded the inner decoder in such a way that the final output error rate is extremely small.
A more detailed explanation of concatenated coding schemes can be found in G. C. Clark, Jr. and J. B. Cain, "Error-Correction Coding for Digital Communications", Plenum Press, New York, 1981; and S. Lin and D. J. Costello, Jr., "Error Control Coding: Fundamentals and Applications", Prentice-Hall, Englewood Cliffs, N.J., 1983. Trellis coding is discussed extensively in G. Ungerboeck, "Channel Coding with Multilevel/Phase Signals", IEEE Transactions on Information Theory, Vol. IT-28, No. 1, pp. 55-67, January 1982; G. Ungerboeck, "Trellis-Coded Modulation with Redundant Signal Sets--Part I: Introduction,--Part II: State of the Art", IEEE Communications Magazine, Vol. 25, No. 2, pp. 5-21, February 1987; and A. R. Caulderbank and N. J. A. Sloane, "New Trellis Codes Based on Lattices and Cosets", IEEE Transactions on Information Theory, Vol. IT-33, No. 2, pp. 177-195, March 1987. The Viterbi algorithm is explained in G. D. Forney, Jr., "The Viterbi Algorithm", Proceedings of the IEEE, Vol. 61, No. 3, March 1973. Reed-Solomon coding systems are discussed in the Clark, Jr. et al and Lin et al texts cited above.
The error rate performance at the output of the inner, modulation code in concatenated coded systems is highly dependent on signal-to-noise ratio (SNR). Some codes perform better, providing a lower error rate, at a low SNR while others perform better at a high SNR. This means that the optimization of the modulation code for concatenated coding systems can lead to different solutions, depending on the specified SNR range. To date, an optimal solution has eluded system designers.
It would be advantageous to provide an optimized data modulation system with high bandwidth efficiency and low power requirements. Such a system should provide a high data rate, with minimal bandwidth occupancy, and very high data reliability. The complexity of a receiver for use with such a system should be minimized, to provide low cost in volume production.
The present invention provides a modulation system having the aforementioned advantages. In particular, the method and apparatus of the present invention provide a concatenated coding implementation wherein the inner trellis coding rate and the outer Reed-Solomon error correction rate are optimized to provide an integer relationship between the various clocks required by the system (enabling a low cost and easily implemented clock design) while achieving excellent coding gain at a desired symbol rate and bandwidth. The invention achieves very high (e.g., 7 dB) coding gain, requires a very small transmission overhead, and provides a simple scheme for Reed-Solomon synchronization, including Reed-Solomon symbol synchronization, block synchronization, interleave block synchronization, trellis symbol synchronization and frame synchronization. These advantages all combine to provide a very robust system that is low in cost, easy to initialize, and allows synchronization to be easily regained if lost.